Solutia oficiala

Problema se rezolva prin metoda programarii dinamice. 
     Fie matricea de intrare X. ncepem cu cteva observatii ajutatoare. Pentru inceput, numarul mic al coloanelor ar trebui sa ne puna pe gnduri. Nu cumva acest fapt ne ajuta la rezolvare? 
     Se observa ca exista cel mult 64 de modalitati de a plasa patrate pe o linie a matricei. De ce 64? Pentru ca patratele trebuie sa fie continute complet n matrice, deci coltul din stnga sus al unui patrat poate fi plasat numai pe coloanele 1, 2, ..., 6. De fapt, acest numar poate fi redus la 37, deoarece unele plasari sunt inutile. De exemplu, nu are sens sa plasam cinci patrate pe o linie, deoarece cel putin unul dintre ele acopera pozitii acoperite si de alte patrate, deci poate fi eliminat, suma elementelor acoperite ramnnd aceeasi. 
     Presupunem ca stim, pentru o anumita linie, sumele maxime care pot fi obtinute plasnd 0, 1, 2, ... K patrate pe liniile 1, 2, ... i si avnd pe linia i o anumita configuratie. Putem determina aceleasi informatii pentru linia i+1 ? 
     Raspunsul este afirmativ si ne ofera rezolvarea problemei. 
     Construim (cel putin teoretic) matricea M[1..N-1,0..K,1..37]. Un element M[i,j,l] reprezinta suma maxima obtinuta plasnd j patrate pe primele i linii, pe ultima linie plasnd configuratia i. 
     M[i+1] se calculeaza pe baza lui M[i]. Pentru a calcula un element din M[i+1] avem nevoie de urmatoarele informatii: 
suma elementelor de pe linia i+2 acoperite de patratele care vor fi plasate pe linia i+1, conform configuratiei l; 
numarul nr[l] al patratelor care duc la configuratia l; 
suma elementelor de pe linia i+1 care sunt acoperite de configuratia l, dar nu si de configuratia c (determinam aceasta informatie pentru orice c); 
valoarea maxima din M pentru fiecare configuratie c plasata pe linia i si continnd j-nr[l] patrate. 
     Modul n care determinam aceste informatii poate fi nteles din sursa. 
     Programul este construit astfel: 
configuratiile posibile de pe o linie sunt plasate n matricea de constante p, iar numarul de patrate din fiecare configuratie, n vectorul nr; 
matricea M este simulata cu ajutorul a doua matrice bidimensionale A si B (adica A=M[i], se calculeaza B=M[i+1], apoi A devine B etc.) 
pentru fiecare rnd unde se pot plasa patrate 
se calculeaza suma adaugata pe rndul respectiv daca plasam o anumita configuratie, n functie de configuratia plasata pe rndul anterior; 
se calculeaza suma adaugata pe rndul URMATOR daca plasam o anumita configuratie pe rndul curent; 
se initializeaza matricea B; 
se realizeaza calculul valorilor din B. Datorita faptului ca operatiile din aceasta zona sunt executate de foarte multe ori, codul trebuie optimizat la maximum. Programul prezentat aici a fost optimizat dupa obtinerea unei versiuni functionale, dar mai lente. Nu s-a mers mai departe cu optimizarea pentru a nu afecta lizibilitatea codului; 
A devine B. 
     Solutia este data de elementul maxim obtinut n final n matricea A. 